package arithmetic.LeetCode;

import java.util.Arrays;

import org.junit.jupiter.api.Test;

/**
 * 在排序数组中查找元素的第一个和最后一个位置
 *
 * 给定一个按照升序排列的整数数组 nums，和一个目标值 target。找出给定目标值在数组中的开始位置和结束位置。
 * 如果数组中不存在目标值 target，返回[-1, -1]。
 *
 * 进阶：
 * 你可以设计并实现时间复杂度为O(log n)的算法解决此问题吗？
 *
 * 示例 1：
 * 输入：nums = [5,7,7,8,8,10], target = 8
 * 输出：[3,4]
 * 示例2：
 *
 * 示例 2：
 * 输入：nums = [5,7,7,8,8,10], target = 6
 * 输出：[-1,-1]
 *
 * 示例 3：
 * 输入：nums = [], target = 0
 * 输出：[-1,-1]
 * 
 *
 * 提示：
 * 0 <= nums.length <= 105
 * -109<= nums[i]<= 109
 * nums是一个非递减数组
 * -109<= target<= 109
 *
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode.cn/problems/find-first-and-last-position-of-element-in-sorted-array
 *
 * @author jiangfeng on 2022/6/5
 */
public class SearchFirstAndLast {

    @Test
    public void test(){
        int[] nums = {5,7,7,8,8,10};
        //System.out.println(searchRange(nums,8));
        System.out.println(Arrays.toString(searchRange(new int[] {1, 2, 3}, 3)));
    }
    public int[] searchRange(int[] nums, int target) {
        return searchRange_(nums,0,nums.length-1,target);
    }

    public int[] searchRange_(int[] nums,int left,int right, int target) {
        if(left>right){
            return new int[]{-1,-1};
        }
        int half =left + (right-left)/2;
        if(nums[half]>target){
            return searchRange_(nums,left,half-1,target);
        }else if(nums[half]<target){
            return searchRange_(nums,half+1,right,target);
        }else{
            //找左边界和右边界
            int l = half;
            while(l-1>=0 && nums[l-1]==target){
                l--;
            }
            int r = half;
            while(r+1<nums.length && nums[r+1]==target){
                r++;
            }
            return new int[]{l,r};

        }
    }


    @Test
    public void test2(){
        int[] nums = {5,7,7,8,8,10};
        //System.out.println(searchRange(nums,8));
        System.out.println(Arrays.toString(searchRange2(new int[] {5,7,7,8,8,10}, 8)));

    }

    /**
     * 项较于1 44.9 MB 只优化了0.2MB的空间
     * 执行用时：0 ms, 在所有 Java 提交中击败了100.00%的用户
     * 内存消耗：44.7 MB, 在所有 Java 提交中击败了22.16%的用户
     * 通过测试用例：88 / 88
     */
    // 非递归二分法
    public int[] searchRange2(int[] nums, int target) {
        int left = 0, right = nums.length - 1;
        while (left <= right) {
            int half = (right + left) / 2;
            if (nums[half] > target) {
                right = half - 1;
            } else if (nums[half] < target) {
                left = half + 1;
            } else {
                //找左边界和右边界
                left=half;
                while (left - 1 >= 0 && nums[left - 1] == target) {
                    left--;
                }
                right=half;
                while (right + 1 < nums.length && nums[right + 1] == target) {
                    right++;
                }
                return new int[] {left, right};
            }
        }
        return new int[] {-1, -1};
    }





}
